By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 30, Issue 5, pp. 1385-1738

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

An O(nlog n) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees

Richard Cole, Martin Farach-Colton, Ramesh Hariharan, Teresa Przytycka, and Mikkel Thorup

pp. 1385-1404

BibTeX  Abstract Full Text:  PDF

The WARM-UP Algorithm: A Lagrangian Construction of Length Restricted Huffman Codes

Ruy Luiz Milidiú and Eduardo Sany Laber

pp. 1405-1426

BibTeX  Abstract Full Text:  PDF

A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction

David Peleg and Vitaly Rubinovich

pp. 1427-1442

BibTeX  Abstract Full Text:  PDF

Fast and Optimal Parallel Multidimensional Search in PRAMs with Applications to Linear Programming and Related Problems

Martin E. Dyer and Sandeep Sen

pp. 1443-1461

BibTeX  Abstract Full Text:  PDF

On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems

Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, and Jan Johannsen

pp. 1462-1484

BibTeX  Abstract Full Text:  PDF

Randomness is Hard

Harry Buhrman and Leen Torenvliet

pp. 1485-1501

BibTeX  Abstract Full Text:  PDF

On the Determinization of Weighted Finite Automata

Adam L. Buchsbaum, Raffaele Giancarlo, and Jeffery R. Westbrook

pp. 1502-1531

BibTeX  Abstract Full Text:  PDF

Algorithms for the Relaxed Online Bin-Packing Model

Giorgio Gambosi, Alberto Postiglione, and Maurizio Talamo

pp. 1532-1551

BibTeX  Abstract Full Text:  PDF

Tight Bounds for Searching a Sorted Array of Strings

Arne Andersson, Torben Hagerup, Johan Håstad, and Ola Petersson

pp. 1552-1578

BibTeX  Abstract Full Text:  PDF

Minimum Networks in Uniform Orientation Metrics

M. Brazil, D. A. Thomas, and J. F. Weng

pp. 1579-1593

BibTeX  Abstract Full Text:  PDF

General Dynamic Routing with Per-Packet Delay Guarantees of O(Distance + 1/Session Rate)

Matthew Andrews, Antonio Fernández, Mor Harchol-Balter, Tom Leighton, and Lisa Zhang

pp. 1594-1623

BibTeX  Abstract Full Text:  PDF

A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems

Avrim Blum, Howard Karloff, Yuval Rabani, and Michael Saks

pp. 1624-1661

BibTeX  Abstract Full Text:  PDF

Linear Time Algorithms for Hamiltonian Problems on (Claw,Net)-Free Graphs

Andreas Brandstädt, Feodor F. Dragan, and Ekkehard Köhler

pp. 1662-1677

BibTeX  Abstract Full Text:  PDF

Squarish k-d Trees

Luc Devroye, Jean Jabbour, and Carlos Zamora-Cura

pp. 1678-1700

BibTeX  Abstract Full Text:  PDF

Computations of Uniform Recurrence Equations Using Minimal Memory Size

Bruno Gaujal, Alain Jean-Marie, and Jean Mairesse

pp. 1701-1738

BibTeX  Abstract Full Text:  PDF